#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

// 三维坐标结构
struct Point3D {
    float x, y, z;
    Point3D(float x_, float y_, float z_) : x(x_), y(y_), z(z_) {}
};

// AP结构
struct AP {
    Point3D pos;
    int channel;
    AP(Point3D p, int c) : pos(p), channel(c) {}
};

// 教学楼参数
const float BUILDING_LEN = 50.0f;   // 长(m)
const float BUILDING_WID = 20.0f;   // 宽(m)
const float FLOOR_HEIGHT = 3.5f;    // 层高(m)
const int FLOORS = 3;               // 楼层数
const float GRID_STEP = 1.0f;       // 网格精度(m)

// 无线参数
const float AP_RADIUS = 8.0f;       // 覆盖半径(m)
const float AP_POWER = -30.0f;      // 发射功率(dBm)
const float MIN_SIGNAL = -70.0f;    // 最小可用信号(dBm)
const vector<int> CHANNELS = {1,6,11}; // 可用信道

// 信号衰减模型 (自由空间损耗)
float calcSignalStrength(Point3D ap, Point3D point) {
    float dist = sqrt(pow(ap.x - point.x, 2) + 
                     pow(ap.y - point.y, 2) + 
                     pow(ap.z - point.z, 2));
    if (dist > AP_RADIUS) return -100.0f; // 超出范围
    
    // 衰减公式: 距离每增加1m衰减2dB
    return AP_POWER - 2 * dist;
}

// 生成三维网格
vector<Point3D> generateGrid() {
    vector<Point3D> grid;
    for (int f = 0; f < FLOORS; f++) {
        float z = f * FLOOR_HEIGHT + FLOOR_HEIGHT/2;
        for (float x = 0; x < BUILDING_LEN; x += GRID_STEP) {
            for (float y = 0; y < BUILDING_WID; y += GRID_STEP) {
                grid.emplace_back(x, y, z);
            }
        }
    }
    return grid;
}

// 贪心算法部署AP
vector<AP> deployAPs(vector<Point3D>& grid) {
    vector<AP> aps;
    vector<bool> covered(grid.size(), false);
    int totalUncovered = grid.size();

    while (totalUncovered > 0) {
        // 找到覆盖最多未覆盖点的位置
        int bestIdx = -1;
        int maxCover = 0;
        Point3D bestPos(0,0,0);

        // 遍历可能的AP位置（网格点）
        for (int i = 0; i < grid.size(); i++) {
            if (covered[i]) continue;
            
            int coverCount = 0;
            for (int j = 0; j < grid.size(); j++) {
                if (!covered[j] && 
                    calcSignalStrength(grid[i], grid[j]) >= MIN_SIGNAL) {
                    coverCount++;
                }
            }

            if (coverCount > maxCover) {
                maxCover = coverCount;
                bestPos = grid[i];
                bestIdx = i;
            }
        }

        // 选择最优信道（避免同频干扰）
        int bestChannel = CHANNELS[0];
        if (!aps.empty()) {
            // 选择与最近AP不同的信道
            float minDist = 1e9;
            for (auto& ap : aps) {
                float dist = sqrt(pow(ap.pos.x - bestPos.x, 2) +
                                 pow(ap.pos.y - bestPos.y, 2) +
                                 pow(ap.pos.z - bestPos.z, 2));
                if (dist < minDist) minDist = dist;
            }
            if (minDist < 2*AP_RADIUS) { // 距离过近，换信道
                bestChannel = (CHANNELS[0] == aps.back().channel) ? CHANNELS[1] : CHANNELS[0];
            }
        }

        // 添加AP并标记覆盖区域
        aps.emplace_back(bestPos, bestChannel);
        for (int j = 0; j < grid.size(); j++) {
            if (!covered[j] && 
                calcSignalStrength(bestPos, grid[j]) >= MIN_SIGNAL) {
                covered[j] = true;
                totalUncovered--;
            }
        }
    }

    return aps;
}

// 绘制信号覆盖热力图
void drawHeatmap(vector<AP>& aps, vector<Point3D>& grid, int floor) {
    int rows = BUILDING_WID / GRID_STEP;
    int cols = BUILDING_LEN / GRID_STEP;
    Mat heatmap(rows, cols, CV_8UC3, Scalar(0,0,0));

    float z = floor * FLOOR_HEIGHT + FLOOR_HEIGHT/2;
    for (auto& p : grid) {
        if (fabs(p.z - z) > 0.1) continue;
        
        // 计算该点最强信号
        float maxSig = -100.0f;
        for (auto& ap : aps) {
            float sig = calcSignalStrength(ap.pos, p);
            if (sig > maxSig) maxSig = sig;
        }

        // 映射信号强度到颜色（红->黄->绿）
        int x = p.x / GRID_STEP;
        int y = rows - 1 - (p.y / GRID_STEP); // 坐标转换
        if (maxSig < MIN_SIGNAL) {
            heatmap.at<Vec3b>(y, x) = Vec3b(0, 0, 0); // 未覆盖（黑）
        } else {
            float ratio = (maxSig - MIN_SIGNAL) / (AP_POWER - MIN_SIGNAL);
            int r = 255 * (1 - ratio);
            int g = 255 * ratio;
            heatmap.at<Vec3b>(y, x) = Vec3b(r, g, 0);
        }
    }

    // 标记AP位置
    for (auto& ap : aps) {
        if (fabs(ap.pos.z - z) > 0.1) continue;
        int x = ap.pos.x / GRID_STEP;
        int y = rows - 1 - (ap.pos.y / GRID_STEP);
        circle(heatmap, Point(x, y), 3, Scalar(0,0,255), -1); // 红色AP
    }

    imshow("Floor " + to_string(floor+1) + " Coverage", heatmap);
    waitKey(0);
}

int main() {
    vector<Point3D> grid = generateGrid();
    vector<AP> aps = deployAPs(grid);

    cout << "部署AP总数: " << aps.size() << endl;
    for (int i = 0; i < aps.size(); i++) {
        cout << "AP" << i+1 << ": (" << aps[i].pos.x << "," 
             << aps[i].pos.y << "," << aps[i].pos.z << ") 信道: " 
             << aps[i].channel << endl;
    }

    // 绘制各楼层热力图
    for (int f = 0; f < FLOORS; f++) {
        drawHeatmap(aps, grid, f);
    }

    return 0;
}